package tree.segmenttree;

/**
 * @Classname : RangeSumQueryMutable02
 * @Description : 307. 区域和检索 - 数组可修改
 * https://leetcode.cn/problems/range-sum-query-mutable/
 * @Author : chentianyu
 * @Date 2022/12/7 21:42
 */

/**
 * 方法二：线段树
 * 适用情况：对单个位置修改
 */
public class RangeSumQueryMutable02 {

    private int[] nums;
    private int n;
    private int[] d;

    public RangeSumQueryMutable02(int[] nums) {
        this.nums = nums;
        n = nums.length;
        d = new int[4 * n];
        build(0, n - 1, 0);
    }

    private void build(int s, int t, int p) {
        // 叶子节点直接为位置p赋值
        if (s == t) {
            d[p] = nums[s];
        }
        // 非叶子节点，递归计算左右子节点值求和后为位置p赋值
        else {
            int m = s + ((t - s) >> 1);
            build(s, m, 2 * p + 1);
            build(m + 1, t, 2 * p + 2);
            d[p] = d[2 * p + 1] + d[2 * p + 2];
        }
    }

    private int search(int l, int r, int s, int t, int p) {
        int sum = 0;
        // 位置p掌管区间在查询区间内，直接返回其掌管区间值
        if (l <= s && t <= r) {
            sum = d[p];
        }
        // 位置p掌管区间不完全在查询区间内，递归左右子节点查询
        else {
            int m = s + ((t - s) >> 1);
            if (l <= m) sum += search(l, r, s, m, 2 * p + 1);
            if (r > m) sum += search(l, r, m + 1, t, 2 * p + 2);
        }
        return sum;
    }

    private void update(int l, int r, int c, int s, int t, int p) {
        // 位置p掌管区间在更新区间内，直接更新其掌管区间值（注意：当l = r时，只会涉及更新叶子节点）
        if (l <= s && t <= r) {
            d[p] = (t - s + 1) * c;
        }
        // 位置p掌管区间不完全在更新区间内，递归左右子节点更新
        else {
            int m = s + ((t - s) >> 1);
            if (l <= m) update(l, r, c, s, m, 2 * p + 1);
            if (r > m) update(l, r, c, m + 1, t, 2 * p + 2);
            d[p] = d[2 * p + 1] + d[2 * p + 2];
        }
    }

    public void update(int index, int val) {
        update(index, index, val, 0, n - 1, 0);
    }

    public int sumRange(int left, int right) {
        return search(left, right, 0, n - 1, 0);
    }
}
